package Preferred_algorithm.Topic3_Binary_Search_algorithm;

public class Topic3_Binary_Search_algorithm {

    // blog：【优选算法 & 二分查找】二分查找算法模板详解
    //https://blog.csdn.net/2402_84916296/article/details/143951072?spm=1001.2014.3001.5501

    //704. 朴素二分查找(朴素二分用于查找单调递增/单调递减的数组)
    //https://leetcode.cn/problems/binary-search/description/
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) { //朴素二分可以 left = right
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    //进阶二分查找：用于查找具有二段性的数组，[ 1 2 2 3 3 3 4 5 ] t=3，就不能用朴素二分


    //34.在排序数组中查找元素的第一个和最后一个位置
    //https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(n==0)return ret;
        // 求左端点
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (nums[right] == target) {
            ret[0] = right;
        }

        left = 0 ;
        right = n - 1; //重新初始化左右指针，这一步是最容易忽略的
        // 求右端点
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (nums[left] == target) {
            ret[1] = left;
        }
        return ret;
    }

    //blog:【优选算法 & 二分查找】二分查找算法入门详解：二分查找小专题
    //https://blog.csdn.net/2402_84916296/article/details/144276684?spm=1001.2014.3001.5501

    //69. x的平方根
    //https://leetcode.cn/problems/sqrtx/
    public int mySqrt(int x) {
        if (x < 1)
            return 0;

        long left = 0, right = x/2; // long 来接收 mid*mid，避免溢出

        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
                left = mid;
            else
                right = mid - 1;
        }
        return (int) left;
    }


    public int mySqrt1(int x) {
        if (x < 1)
            return 0;

        if (x == 1)
            return 1;

        long left = 0;
        long right = x / 2; //优化：sqrt(x) <= (x/2)
        // long 来接收 mid*mid，避免溢出

        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
                left = mid;
            else
                right = mid - 1;
        }
        return (int) left;
    }
    //35.搜索插入位置
    //https://leetcode.cn/problems/search-insert-position/
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        if (target < nums[0])
            return 0;
        if (target > nums[n - 1])
            return n;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        if (nums[left] == target)
            return left;
        else
            return left + 1;
    }

    //852.山脉数组的峰顶索引
    //https://leetcode.cn/problems/peak-index-in-a-mountain-array/
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        if (n == 1)
            return 0;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] >= arr[mid - 1])
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }

    // 162. 寻找峰值
    //https://leetcode.cn/problems/find-peak-element/
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n==1)return 0;
        if(nums[0]>nums[1])return 0;
        if(nums[n-1]>nums[n-2])return n-1;

        int left = 0 ;
        int right = n-1;
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(nums[mid]>=nums[mid-1])left = mid;
            else right = mid - 1;
        }
        return left;
    }

    //153.寻找旋转排序数组中的最小值
    //https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
    public int findMin(int[] nums) {
        int n = nums.length;
        if(n==1)return nums[0];

        int left = 0 , right = n-1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid]<=nums[n-1])right = mid;
            else left = mid + 1;
        }
        return nums[left];
    }

    //LCR 173.点名
    //https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

    //方法一: 位运算异或
    public int takeAttendance(int[] records) {
        int ret = 0;
        for (int x : records)
            ret ^= x;
        for (int i = 0; i < records.length + 1; i++)
            ret ^= i;
        return ret;
    }

    //方法二: 二分查找
    public int takeAttendance1(int[] records) {
        int n = records.length;

        if (records[0] == 1)
            return 0;

        int left = 0, right = n - 1;

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (records[mid] <= mid)
                left = mid;
            else
                right = mid - 1;
        }
        return left + 1;
    }

}
